package com.atguigu.tree;

import com.atguigu.array.Array;
import com.atguigu.map.AVLMap;
import com.atguigu.map.BSTMap;

import java.util.ArrayList;
import java.util.List;
import java.util.Random;

public class RBTreeTest {

    public static void main(String[] args) {
        testTree();

    }

    /***
     * 测试 BSTree、AVLTree、BRTree 添加数据的性能
     */
    public static void testTree() {
        int n=20000000;
        Random random=new Random();
        List<Integer> testData=new ArrayList<>();
        for(int i=0;i<n;i++){
            testData.add(random.nextInt(Integer.MAX_VALUE));
        }
        long startTime=System.nanoTime();
        BSTMap<Integer,Integer> bst=new BSTMap<>();
        for(Integer x:testData){
            bst.add(x,null);
        }
        long endTime=System.nanoTime();
        double time=(endTime-startTime)/1000000000.0;
        System.out.println("BST: "+time+" s");
        System.out.println("=====================================");
        long startTime1=System.nanoTime();
        AVLMap<Integer,Integer> avl=new AVLMap<>();
        for(Integer x:testData){
            avl.add(x,null);
        }
        long endTime1=System.nanoTime();
        double time1=(endTime1-startTime1)/1000000000.0;
        System.out.println("AVL: "+time1+" s");
        System.out.println("=====================================");
        long startTime2=System.nanoTime();
        RBTree<Integer,Integer> rbt=new RBTree<>();
        for(Integer x:testData){
            rbt.add(x,null);
        }
        long endTime2=System.nanoTime();
        double time2=(endTime2-startTime2)/1000000000.0;
        System.out.println("RBTree: "+time2+" s");
    }
}
